<!DOCTYPE html>
<html lang="zh-CN" data-theme="light">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width,initial-scale=1" />
    <meta name="generator" content="VuePress 2.0.0-beta.38" />
    <meta name="theme" content="VuePress Theme Hope" />
    <meta property="og:url" content="https://javaguide.cn/cs-basics/data-structure/heap.html"><meta property="og:site_name" content="JavaGuide"><meta property="og:title" content="堆"><meta property="og:type" content="article"><meta property="og:image" content="https://javaguide.cn/"><meta property="og:updated_time" content="2022-03-03T01:14:56.000Z"><meta property="og:locale" content="zh-CN"><meta name="twitter:card" content="summary_large_image"><meta name="twitter:image:alt" content="堆"><meta property="article:tag" content="数据结构"><meta property="article:modified_time" content="2022-03-03T01:14:56.000Z"><script>var _hmt = _hmt || [];
      (function() {
        var hm = document.createElement("script");
        hm.src = "https://hm.baidu.com/hm.js?5dd2e8c97962d57b7b8fea1737c01743";
        var s = document.getElementsByTagName("script")[0]; 
        s.parentNode.insertBefore(hm, s);
      })();</script><link rel="stylesheet" href="//at.alicdn.com/t/font_2922463_99aa80ii7cf.css"><title>堆 | JavaGuide</title><meta name="description" content="Java学习&&面试指南">
    <style>
      :root {
        --bg-color: #fff;
      }

      html[data-theme="dark"] {
        --bg-color: #1d2025;
      }

      html,
      body {
        background-color: var(--bg-color);
      }
    </style>
    <script>
      const userMode = localStorage.getItem("vuepress-theme-hope-scheme");
      const systemDarkMode =
        window.matchMedia &&
        window.matchMedia("(prefers-color-scheme: dark)").matches;

      if (userMode === "dark" || (userMode !== "light" && systemDarkMode)) {
        document.querySelector("html").setAttribute("data-theme", "dark");
      }
    </script>
    <link rel="stylesheet" href="/assets/style.aa943f56.css">
    <link rel="modulepreload" href="/assets/app.93341f6d.js"><link rel="modulepreload" href="/assets/heap.html.54637231.js"><link rel="modulepreload" href="/assets/heap.html.1220dc01.js"><link rel="modulepreload" href="/assets/plugin-vue_export-helper.21dcd24c.js">
  </head>
  <body>
    <div id="app"><!--[--><!--[--><!--[--><span tabindex="-1"></span><a href="#main-content" class="skip-link sr-only">Skip to content</a><!--]--><div class="theme-container has-toc sidebar-open"><!--[--><header class="navbar"><button class="toggle-sidebar-button" title="Toggle Sidebar"><span class="icon"></span></button><a href="/" class="home-link"><img class="logo" src="/logo.png" alt="JavaGuide"><!----><span class="site-name hide-in-pad">JavaGuide</span><!--[--><!----><!--]--></a><nav class="nav-links" style=""><div class="nav-item hide-in-mobile"><a href="/home.html" class="nav-link" arialabel="面试指南"><i class="icon iconfont icon-java"></i>面试指南<!----></a></div><div class="nav-item hide-in-mobile"><a href="/zhuanlan/" class="nav-link" arialabel="优质专栏"><i class="icon iconfont icon-recommend"></i>优质专栏<!----></a></div><div class="nav-item hide-in-mobile"><a href="/open-source-project/" class="nav-link" arialabel="项目精选"><i class="icon iconfont icon-github"></i>项目精选<!----></a></div><div class="nav-item hide-in-mobile"><a href="/books/" class="nav-link" arialabel="书籍精选"><i class="icon iconfont icon-book"></i>书籍精选<!----></a></div><div class="nav-item hide-in-mobile"><a href="https://snailclimb.gitee.io/javaguide/#/" rel="noopener noreferrer" target="_blank" arialabel="旧版链接" class="nav-link"><i class="icon iconfont icon-java"></i>旧版链接<span><svg class="external-link-icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewbox="0 0 100 100" width="15" height="15"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path><polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg><span class="external-link-icon-sr-only">open in new window</span></span><!----></a></div><div class="nav-item hide-in-mobile"><a href="https://javaguide.cn/feed.json" rel="noopener noreferrer" target="_blank" arialabel="RSS订阅" class="nav-link"><i class="icon iconfont icon-rss"></i>RSS订阅<span><svg class="external-link-icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewbox="0 0 100 100" width="15" height="15"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path><polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg><span class="external-link-icon-sr-only">open in new window</span></span><!----></a></div><div class="nav-item hide-in-mobile"><a href="/about-the-author/" class="nav-link" arialabel="关于作者"><i class="icon iconfont icon-zuozhe"></i>关于作者<!----></a></div></nav><div class="nav-actions-wrapper"><!--[--><!----><!--]--><div class="nav-item"><!----></div><div class="nav-item"><a class="repo-link" href="https://github.com/Snailclimb/JavaGuide" target="_blank" rel="noopener noreferrer"><svg xmlns="http://www.w3.org/2000/svg" class="icon github-icon" viewbox="0 0 1024 1024" arialabelledby="github" style="width:1.25rem;height:1.25rem;vertical-align:middle;"><title id="github" lang="en">github icon</title><g fill="currentColor"><path d="M511.957 21.333C241.024 21.333 21.333 240.981 21.333 512c0 216.832 140.544 400.725 335.574 465.664 24.49 4.395 32.256-10.07 32.256-23.083 0-11.69.256-44.245 0-85.205-136.448 29.61-164.736-64.64-164.736-64.64-22.315-56.704-54.4-71.765-54.4-71.765-44.587-30.464 3.285-29.824 3.285-29.824 49.195 3.413 75.179 50.517 75.179 50.517 43.776 75.008 114.816 53.333 142.762 40.79 4.523-31.66 17.152-53.377 31.19-65.537-108.971-12.458-223.488-54.485-223.488-242.602 0-53.547 19.114-97.323 50.517-131.67-5.035-12.33-21.93-62.293 4.779-129.834 0 0 41.258-13.184 134.912 50.346a469.803 469.803 0 0 1 122.88-16.554c41.642.213 83.626 5.632 122.88 16.554 93.653-63.488 134.784-50.346 134.784-50.346 26.752 67.541 9.898 117.504 4.864 129.834 31.402 34.347 50.474 78.123 50.474 131.67 0 188.586-114.73 230.016-224.042 242.09 17.578 15.232 33.578 44.672 33.578 90.454v135.85c0 13.142 7.936 27.606 32.854 22.87C862.25 912.597 1002.667 728.747 1002.667 512c0-271.019-219.648-490.667-490.71-490.667z"></path></g></svg></a></div><div class="nav-item hide-in-mobile"><button id="appearance-switch"><svg xmlns="http://www.w3.org/2000/svg" class="icon auto-icon" viewbox="0 0 1024 1024" arialabelledby="auto" style="display:block;"><title id="auto" lang="en">auto icon</title><g fill="currentColor"><path d="M512 992C246.92 992 32 777.08 32 512S246.92 32 512 32s480 214.92 480 480-214.92 480-480 480zm0-840c-198.78 0-360 161.22-360 360 0 198.84 161.22 360 360 360s360-161.16 360-360c0-198.78-161.22-360-360-360zm0 660V212c165.72 0 300 134.34 300 300 0 165.72-134.28 300-300 300z"></path></g></svg><svg xmlns="http://www.w3.org/2000/svg" class="icon dark-icon" viewbox="0 0 1024 1024" arialabelledby="dark" style="display:none;"><title id="dark" lang="en">dark icon</title><g fill="currentColor"><path d="M524.8 938.667h-4.267a439.893 439.893 0 0 1-313.173-134.4 446.293 446.293 0 0 1-11.093-597.334A432.213 432.213 0 0 1 366.933 90.027a42.667 42.667 0 0 1 45.227 9.386 42.667 42.667 0 0 1 10.24 42.667 358.4 358.4 0 0 0 82.773 375.893 361.387 361.387 0 0 0 376.747 82.774 42.667 42.667 0 0 1 54.187 55.04 433.493 433.493 0 0 1-99.84 154.88 438.613 438.613 0 0 1-311.467 128z"></path></g></svg><svg xmlns="http://www.w3.org/2000/svg" class="icon light-icon" viewbox="0 0 1024 1024" arialabelledby="light" style="display:none;"><title id="light" lang="en">light icon</title><g fill="currentColor"><path d="M952 552h-80a40 40 0 0 1 0-80h80a40 40 0 0 1 0 80zM801.88 280.08a41 41 0 0 1-57.96-57.96l57.96-58a41.04 41.04 0 0 1 58 58l-58 57.96zM512 752a240 240 0 1 1 0-480 240 240 0 0 1 0 480zm0-560a40 40 0 0 1-40-40V72a40 40 0 0 1 80 0v80a40 40 0 0 1-40 40zm-289.88 88.08-58-57.96a41.04 41.04 0 0 1 58-58l57.96 58a41 41 0 0 1-57.96 57.96zM192 512a40 40 0 0 1-40 40H72a40 40 0 0 1 0-80h80a40 40 0 0 1 40 40zm30.12 231.92a41 41 0 0 1 57.96 57.96l-57.96 58a41.04 41.04 0 0 1-58-58l58-57.96zM512 832a40 40 0 0 1 40 40v80a40 40 0 0 1-80 0v-80a40 40 0 0 1 40-40zm289.88-88.08 58 57.96a41.04 41.04 0 0 1-58 58l-57.96-58a41 41 0 0 1 57.96-57.96z"></path></g></svg></button></div><form class="search-box" role="search"><input type="search" placeholder="搜索" autocomplete="off" spellcheck="false" value><!----></form><button class="toggle-navbar-button" aria-label="Toggle Navbar" aria-expanded="false" aria-controls="nav-screen"><span class="button-container"><span class="button-top"></span><span class="button-middle"></span><span class="button-bottom"></span></span></button><!--[--><!----><!--]--></div></header><!----><!--]--><!----><div class="toggle-sidebar-wrapper"><span class="arrow left"></span></div><aside class="sidebar"><!--[--><!----><!--]--><ul class="sidebar-links"><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-mianshi"></i><span class="title">面试准备</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-java"></i><span class="title">Java</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable active"><i class="icon iconfont icon-computer"></i><span class="title">计算机基础</span><span class="arrow down"></span></button><ul class="sidebar-links"><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-network"></i><span class="title">网络</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-caozuoxitong"></i><span class="title">操作系统</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable active"><i class="icon iconfont icon-people-network-full"></i><span class="title">数据结构</span><span class="arrow down"></span></button><ul class="sidebar-links"><li><!--[--><a href="/cs-basics/data-structure/linear-data-structure.html" class="nav-link sidebar-link sidebar-page" arialabel="线性数据结构 :数组、链表、栈、队列"><!---->线性数据结构 :数组、链表、栈、队列<!----></a><ul class="sidebar-sub-headers"></ul><!--]--></li><li><!--[--><a href="/cs-basics/data-structure/graph.html" class="nav-link sidebar-link sidebar-page" arialabel="图"><!---->图<!----></a><ul class="sidebar-sub-headers"></ul><!--]--></li><li><!--[--><a aria-current="page" href="/cs-basics/data-structure/heap.html" class="router-link-active router-link-exact-active nav-link active sidebar-link sidebar-page active" arialabel="堆"><!---->堆<!----></a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/heap.html#什么是堆" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="什么是堆"><!---->什么是堆<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/heap.html#堆的用途" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="堆的用途"><!---->堆的用途<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/heap.html#堆的分类" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="堆的分类"><!---->堆的分类<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/heap.html#堆的存储" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="堆的存储"><!---->堆的存储<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/heap.html#堆的操作" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="堆的操作"><!---->堆的操作<!----></a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/heap.html#插入元素" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="插入元素"><!---->插入元素<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/heap.html#删除堆顶元素" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="删除堆顶元素"><!---->删除堆顶元素<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/heap.html#堆的操作总结" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="堆的操作总结"><!---->堆的操作总结<!----></a><ul class="sidebar-sub-headers"></ul></li></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/heap.html#堆排序" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="堆排序"><!---->堆排序<!----></a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/heap.html#建堆" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="建堆"><!---->建堆<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/cs-basics/data-structure/heap.html#排序" class="router-link-active router-link-exact-active nav-link sidebar-link heading" arialabel="排序"><!---->排序<!----></a><ul class="sidebar-sub-headers"></ul></li></ul></li></ul><!--]--></li><li><!--[--><a href="/cs-basics/data-structure/tree.html" class="nav-link sidebar-link sidebar-page" arialabel="树"><!---->树<!----></a><ul class="sidebar-sub-headers"></ul><!--]--></li><li><!--[--><a href="/cs-basics/data-structure/red-black-tree.html" class="nav-link sidebar-link sidebar-page" arialabel="红黑树"><!---->红黑树<!----></a><ul class="sidebar-sub-headers"></ul><!--]--></li><li><!--[--><a href="/cs-basics/data-structure/bloom-filter.html" class="nav-link sidebar-link sidebar-page" arialabel="布隆过滤器"><!---->布隆过滤器<!----></a><ul class="sidebar-sub-headers"></ul><!--]--></li></ul></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-suanfaku"></i><span class="title">算法</span><span class="arrow right"></span></button><!----></section><!--]--></li></ul></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-database"></i><span class="title">数据库</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-Tools"></i><span class="title">开发工具</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-xitongsheji"></i><span class="title">系统设计</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-distributed-network"></i><span class="title">分布式</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-et-performance"></i><span class="title">高性能</span><span class="arrow right"></span></button><!----></section><!--]--></li><li><!--[--><section class="sidebar-group"><button class="sidebar-heading clickable"><i class="icon iconfont icon-CalendarAvailability-1"></i><span class="title">高可用</span><span class="arrow right"></span></button><!----></section><!--]--></li></ul><!--[--><!----><!--]--></aside><!--[--><main class="page" id="main-content"><!----><nav class="breadcrumb disable"></nav><div class="page-title"><h1><!---->堆</h1><div class="article-info"><span class="author-info" arialabel="作者🖊" isoriginal="false" pageview="false" color="false"><svg xmlns="http://www.w3.org/2000/svg" class="icon author-icon" viewbox="0 0 1024 1024" arialabelledby="author"><title id="author" lang="en">author icon</title><g fill="currentColor"><path d="M649.6 633.6c86.4-48 147.2-144 147.2-249.6 0-160-128-288-288-288s-288 128-288 288c0 108.8 57.6 201.6 147.2 249.6-121.6 48-214.4 153.6-240 288-3.2 9.6 0 19.2 6.4 25.6 3.2 9.6 12.8 12.8 22.4 12.8h704c9.6 0 19.2-3.2 25.6-12.8 6.4-6.4 9.6-16 6.4-25.6-25.6-134.4-121.6-240-243.2-288z"></path></g></svg><span><a class="author-item" href="https://javaguide.cn/" target="_blank" rel="noopener noreferrer">Guide</a></span><span property="author" content="Guide"></span></span><span class="category-info" arialabel="分类🌈" isoriginal="false" pageview="false"><svg xmlns="http://www.w3.org/2000/svg" class="icon category-icon" viewbox="0 0 1024 1024" arialabelledby="category"><title id="category" lang="en">category icon</title><g fill="currentColor"><path d="M148.41 106.992h282.176c22.263 0 40.31 18.048 40.31 40.31V429.48c0 22.263-18.047 40.31-40.31 40.31H148.41c-22.263 0-40.311-18.047-40.311-40.31V147.302c0-22.263 18.048-40.31 40.311-40.31zM147.556 553.478H429.73c22.263 0 40.311 18.048 40.311 40.31v282.176c0 22.263-18.048 40.312-40.31 40.312H147.555c-22.263 0-40.311-18.049-40.311-40.312V593.79c0-22.263 18.048-40.311 40.31-40.311zM593.927 106.992h282.176c22.263 0 40.31 18.048 40.31 40.31V429.48c0 22.263-18.047 40.31-40.31 40.31H593.927c-22.263 0-40.311-18.047-40.311-40.31V147.302c0-22.263 18.048-40.31 40.31-40.31zM730.22 920.502H623.926c-40.925 0-74.22-33.388-74.22-74.425V623.992c0-41.038 33.387-74.424 74.425-74.424h222.085c41.038 0 74.424 33.226 74.424 74.067v114.233c0 10.244-8.304 18.548-18.547 18.548s-18.548-8.304-18.548-18.548V623.635c0-20.388-16.746-36.974-37.33-36.974H624.13c-20.585 0-37.331 16.747-37.331 37.33v222.086c0 20.585 16.654 37.331 37.126 37.331H730.22c10.243 0 18.547 8.304 18.547 18.547 0 10.244-8.304 18.547-18.547 18.547z"></path></g></svg><ul class="categories-wrapper"><li class="category clickable" role="navigation">计算机基础</li><meta property="articleSection" content="计算机基础"></ul></span><span arialabel="标签🏷" isoriginal="false" pageview="false"><svg xmlns="http://www.w3.org/2000/svg" class="icon tag-icon" viewbox="0 0 1024 1024" arialabelledby="tag"><title id="tag" lang="en">tag icon</title><g fill="currentColor"><path d="M939.902 458.563L910.17 144.567c-1.507-16.272-14.465-29.13-30.737-30.737L565.438 84.098h-.402c-3.215 0-5.726 1.005-7.634 2.913l-470.39 470.39a10.004 10.004 0 000 14.164l365.423 365.424c1.909 1.908 4.42 2.913 7.132 2.913s5.223-1.005 7.132-2.913l470.39-470.39c2.01-2.11 3.014-5.023 2.813-8.036zm-240.067-72.121c-35.458 0-64.286-28.828-64.286-64.286s28.828-64.285 64.286-64.285 64.286 28.828 64.286 64.285-28.829 64.286-64.286 64.286z"></path></g></svg><ul class="tags-wrapper"><li class="tag clickable" role="navigation">数据结构</li></ul><meta property="keywords" content="数据结构"></span><span class="date-info" arialabel="写作日期📅" isoriginal="false" pageview="false" color="false"><svg xmlns="http://www.w3.org/2000/svg" class="icon calendar-icon" viewbox="0 0 1024 1024" arialabelledby="calendar"><title id="calendar" lang="en">calendar icon</title><g fill="currentColor"><path d="M716.4 110.137c0-18.753-14.72-33.473-33.472-33.473-18.753 0-33.473 14.72-33.473 33.473v33.473h66.993v-33.473zm-334.87 0c0-18.753-14.72-33.473-33.473-33.473s-33.52 14.72-33.52 33.473v33.473h66.993v-33.473zm468.81 33.52H716.4v100.465c0 18.753-14.72 33.473-33.472 33.473a33.145 33.145 0 01-33.473-33.473V143.657H381.53v100.465c0 18.753-14.72 33.473-33.473 33.473a33.145 33.145 0 01-33.473-33.473V143.657H180.6A134.314 134.314 0 0046.66 277.595v535.756A134.314 134.314 0 00180.6 947.289h669.74a134.36 134.36 0 00133.94-133.938V277.595a134.314 134.314 0 00-133.94-133.938zm33.473 267.877H147.126a33.145 33.145 0 01-33.473-33.473c0-18.752 14.72-33.473 33.473-33.473h736.687c18.752 0 33.472 14.72 33.472 33.473a33.145 33.145 0 01-33.472 33.473z"></path></g></svg><span>2022年3月3日</span><meta property="datePublished" content="2022-03-03T01:14:56.000Z"></span><!----><span class="words-info" arialabel="字数🔠" isoriginal="false" pageview="false" color="false"><svg xmlns="http://www.w3.org/2000/svg" class="icon word-icon" viewbox="0 0 1024 1024" arialabelledby="word"><title id="word" lang="en">word icon</title><g fill="currentColor"><path d="M518.217 432.64V73.143A73.143 73.143 0 01603.43 1.097a512 512 0 01419.474 419.474 73.143 73.143 0 01-72.046 85.212H591.36a73.143 73.143 0 01-73.143-73.143z"></path><path d="M493.714 566.857h340.297a73.143 73.143 0 0173.143 85.577A457.143 457.143 0 11371.566 117.76a73.143 73.143 0 0185.577 73.143v339.383a36.571 36.571 0 0036.571 36.571z"></path></g></svg><span>约 2696 字</span><meta property="wordCount" content="2696"></span></div><hr></div><div class="toc-place-holder"><aside id="toc-list"><div class="toc-header">此页内容</div><div class="toc-wrapper"><ul class="toc-list"><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/heap.html#什么是堆" class="router-link-active router-link-exact-active toc-link level2">什么是堆</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/heap.html#堆的用途" class="router-link-active router-link-exact-active toc-link level2">堆的用途</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/heap.html#堆的分类" class="router-link-active router-link-exact-active toc-link level2">堆的分类</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/heap.html#堆的存储" class="router-link-active router-link-exact-active toc-link level2">堆的存储</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/heap.html#堆的操作" class="router-link-active router-link-exact-active toc-link level2">堆的操作</a></li><ul class="toc-list"><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/heap.html#插入元素" class="router-link-active router-link-exact-active toc-link level3">插入元素</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/heap.html#删除堆顶元素" class="router-link-active router-link-exact-active toc-link level3">删除堆顶元素</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/heap.html#堆的操作总结" class="router-link-active router-link-exact-active toc-link level3">堆的操作总结</a></li><!----><!--]--></ul><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/heap.html#堆排序" class="router-link-active router-link-exact-active toc-link level2">堆排序</a></li><ul class="toc-list"><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/heap.html#建堆" class="router-link-active router-link-exact-active toc-link level3">建堆</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/cs-basics/data-structure/heap.html#排序" class="router-link-active router-link-exact-active toc-link level3">排序</a></li><!----><!--]--></ul><!--]--></ul></div></aside></div><!----><div class="theme-hope-content"><!--[--><h1 id="堆" tabindex="-1"><a class="header-anchor" href="#堆" aria-hidden="true">#</a> 堆</h1><h2 id="什么是堆" tabindex="-1"><a class="header-anchor" href="#什么是堆" aria-hidden="true">#</a> 什么是堆</h2><p>堆是一种满足以下条件的树：</p><p>堆中的每一个节点值都大于等于（或小于等于）子树中所有节点的值。或者说，任意一个节点的值都大于等于（或小于等于）所有子节点的值。</p><blockquote><p>大家可以把堆(最大堆)理解为一个公司,这个公司很公平,谁能力强谁就当老大,不存在弱的人当老大,老大手底下的人一定不会比他强。这样有助于理解后续堆的操作。</p></blockquote><p><strong>!!!特别提示：</strong></p><ul><li>很多博客说堆是完全二叉树，其实并非如此，<strong>堆不一定是完全二叉树</strong>，只是为了方便存储和索引，我们通常用完全二叉树的形式来表示堆，事实上，广为人知的斐波那契堆和二项堆就不是完全二叉树,它们甚至都不是二叉树。</li><li>（<strong>二叉</strong>）堆是一个数组，它可以被看成是一个 <strong>近似的完全二叉树</strong>。——《算法导论》第三版</li></ul><p>大家可以尝试判断下面给出的图是否是堆？</p><p><img src="/assets/堆1.1da7c32c.png" alt="" loading="lazy"></p><p>第1个和第2个是堆。第1个是最大堆，每个节点都比子树中所有节点大。第2个是最小堆，每个节点都比子树中所有节点小。</p><p>第3个不是，第三个中，根结点1比2和15小，而15却比3大，19比5大，不满足堆的性质。</p><h2 id="堆的用途" tabindex="-1"><a class="header-anchor" href="#堆的用途" aria-hidden="true">#</a> 堆的用途</h2><p>当我们只关心所有数据中的最大值或者最小值，存在多次获取最大值或者最小值，多次插入或删除数据时，就可以使用堆。</p><p>有小伙伴可能会想到用有序数组，初始化一个有序数组时间复杂度是 <code>O(nlog(n))</code>，查找最大值或者最小值时间复杂度都是 <code>O(1)</code>，但是，涉及到更新（插入或删除）数据时，时间复杂度为 <code>O(n)</code>，即使是使用复杂度为 <code>O(log(n))</code> 的二分法找到要插入或者删除的数据，在移动数据时也需要 <code>O(n)</code> 的时间复杂度。</p><p><strong>相对于有序数组而言，堆的主要优势在于更新数据效率较高。</strong> 堆的初始化时间复杂度为 <code>O(nlog(n))</code>，堆可以做到<code>O(1)</code>时间复杂度取出最大值或者最小值，<code>O(log(n))</code>时间复杂度插入或者删除数据，具体操作在后续章节详细介绍。</p><h2 id="堆的分类" tabindex="-1"><a class="header-anchor" href="#堆的分类" aria-hidden="true">#</a> 堆的分类</h2><p>堆分为 <strong>最大堆</strong> 和 <strong>最小堆</strong>。二者的区别在于节点的排序方式。</p><ul><li><strong>最大堆</strong> ：堆中的每一个节点的值都大于等于子树中所有节点的值</li><li><strong>最小堆</strong> ：堆中的每一个节点的值都小于等于子树中所有节点的值</li></ul><p>如下图所示，图1是最大堆，图2是最小堆</p><p><img src="/assets/堆2.66dd01d8.png" alt="" loading="lazy"></p><h2 id="堆的存储" tabindex="-1"><a class="header-anchor" href="#堆的存储" aria-hidden="true">#</a> 堆的存储</h2><p>之前介绍树的时候说过，由于完全二叉树的优秀性质，利用数组存储二叉树即节省空间，又方便索引（若根结点的序号为1，那么对于树中任意节点i，其左子节点序号为 <code>2*i</code>，右子节点序号为 <code>2*i+1</code>）。</p><p>为了方便存储和索引，（二叉）堆可以用完全二叉树的形式进行存储。存储的方式如下图所示：</p><p><img src="/assets/堆的存储.03237dbe.png" alt="堆的存储" loading="lazy"></p><h2 id="堆的操作" tabindex="-1"><a class="header-anchor" href="#堆的操作" aria-hidden="true">#</a> 堆的操作</h2><p>堆的更新操作主要包括两种 : <strong>插入元素</strong> 和 <strong>删除堆顶元素</strong>。操作过程需要着重掌握和理解。</p><blockquote><p>在进入正题之前，再重申一遍，堆是一个公平的公司，有能力的人自然会走到与他能力所匹配的位置</p></blockquote><h3 id="插入元素" tabindex="-1"><a class="header-anchor" href="#插入元素" aria-hidden="true">#</a> 插入元素</h3><blockquote><p>插入元素，作为一个新入职的员工，初来乍到，这个员工需要从基层做起</p></blockquote><p><strong>1.将要插入的元素放到最后</strong></p><p><img src="/assets/堆-插入元素1.9a9e88c3.png" alt="堆-插入元素-1" loading="lazy"></p><blockquote><p>有能力的人会逐渐升职加薪，是金子总会发光的！！！</p></blockquote><p><strong>2.从底向上，如果父结点比该元素大，则该节点和父结点交换，直到无法交换</strong></p><p><img src="/assets/堆-插入元素2.7e937b5e.png" alt="堆-插入元素2" loading="lazy"></p><p><img src="/assets/堆-插入元素3.8e0739cc.png" alt="堆-插入元素3" loading="lazy"></p><h3 id="删除堆顶元素" tabindex="-1"><a class="header-anchor" href="#删除堆顶元素" aria-hidden="true">#</a> 删除堆顶元素</h3><p>根据堆的性质可知，最大堆的堆顶元素为所有元素中最大的，最小堆的堆顶元素是所有元素中最小的。当我们需要多次查找最大元素或者最小元素的时候，可以利用堆来实现。</p><p>删除堆顶元素后，为了保持堆的性质，需要对堆的结构进行调整，我们将这个过程称之为&quot;<strong>堆化</strong>&quot;，堆化的方法分为两种：</p><ul><li>一种是自底向上的堆化，上述的插入元素所使用的就是自底向上的堆化，元素从最底部向上移动。</li><li>另一种是自顶向下堆化，元素由最顶部向下移动。在讲解删除堆顶元素的方法时，我将阐述这两种操作的过程，大家可以体会一下二者的不同。</li></ul><h4 id="自底向上堆化" tabindex="-1"><a class="header-anchor" href="#自底向上堆化" aria-hidden="true">#</a> 自底向上堆化</h4><blockquote><p>在堆这个公司中，会出现老大离职的现象，老大离职之后，他的位置就空出来了</p></blockquote><p>首先删除堆顶元素，使得数组中下标为1的位置空出。</p><p><img src="/assets/删除堆顶元素1.cd68b7ff.png" alt="删除堆顶元素1" loading="lazy"></p><blockquote><p>那么他的位置由谁来接替呢，当然是他的直接下属了，谁能力强就让谁上呗</p></blockquote><p>比较根结点的左子节点和右子节点，也就是下标为2,3的数组元素，将较大的元素填充到根结点(下标为1)的位置。</p><p><img src="/assets/删除堆顶元素2.59fc6629.png" alt="删除堆顶元素2" loading="lazy"></p><blockquote><p>这个时候又空出一个位置了，老规矩，谁有能力谁上</p></blockquote><p>一直循环比较空出位置的左右子节点，并将较大者移至空位，直到堆的最底部</p><p><img src="/assets/删除堆顶元素3.b5c78c7d.png" alt="删除堆顶元素3" loading="lazy"></p><p>这个时候已经完成了自底向上的堆化，没有元素可以填补空缺了，但是，我们可以看到数组中出现了“气泡”，这会导致存储空间的浪费。接下来我们试试自顶向下堆化。</p><h4 id="自顶向下堆化" tabindex="-1"><a class="header-anchor" href="#自顶向下堆化" aria-hidden="true">#</a> 自顶向下堆化</h4><p>自顶向下的堆化用一个词形容就是“石沉大海”，那么第一件事情，就是把石头抬起来，从海面扔下去。这个石头就是堆的最后一个元素，我们将最后一个元素移动到堆顶。</p><p><img src="/assets/删除堆顶元素4.90633757.png" alt="删除堆顶元素4" loading="lazy"></p><p>然后开始将这个石头沉入海底，不停与左右子节点的值进行比较，和较大的子节点交换位置，直到无法交换位置。</p><p><img src="/assets/删除堆顶元素5.ca1fc0c4.png" alt="删除堆顶元素5" loading="lazy"></p><p><img src="/assets/删除堆顶元素6.9549fe90.png" alt="删除堆顶元素6" loading="lazy"></p><h3 id="堆的操作总结" tabindex="-1"><a class="header-anchor" href="#堆的操作总结" aria-hidden="true">#</a> 堆的操作总结</h3><ul><li><strong>插入元素</strong> ：先将元素放至数组末尾，再自底向上堆化，将末尾元素上浮</li><li><strong>删除堆顶元素</strong> ：删除堆顶元素，将末尾元素放至堆顶，再自顶向下堆化，将堆顶元素下沉。也可以自底向上堆化，只是会产生“气泡”，浪费存储空间。最好采用自顶向下堆化的方式。</li></ul><h2 id="堆排序" tabindex="-1"><a class="header-anchor" href="#堆排序" aria-hidden="true">#</a> 堆排序</h2><p>堆排序的过程分为两步：</p><ul><li>第一步是建堆，将一个无序的数组建立为一个堆</li><li>第二步是排序，将堆顶元素取出，然后对剩下的元素进行堆化，反复迭代，直到所有元素被取出为止。</li></ul><h3 id="建堆" tabindex="-1"><a class="header-anchor" href="#建堆" aria-hidden="true">#</a> 建堆</h3><p>如果你已经足够了解堆化的过程，那么建堆的过程掌握起来就比较容易了。建堆的过程就是一个对所有非叶节点的自顶向下堆化过程。</p><p>首先要了解哪些是非叶节点，最后一个节点的父结点及它之前的元素，都是非叶节点。也就是说，如果节点个数为n，那么我们需要对n/2到1的节点进行自顶向下（沉底）堆化。</p><p>具体过程如下图：</p><p><img src="/assets/建堆1.87738933.png" alt="建堆1" loading="lazy"></p><p>将初始的无序数组抽象为一棵树，图中的节点个数为6，所以4,5,6节点为叶节点，1,2,3节点为非叶节点，所以要对1-3号节点进行自顶向下（沉底）堆化，注意，顺序是从后往前堆化，从3号节点开始，一直到1号节点。 3号节点堆化结果：</p><p><img src="/assets/建堆2.f6cd7436.png" alt="建堆1" loading="lazy"></p><p>2号节点堆化结果：</p><p><img src="/assets/建堆3.476a908d.png" alt="建堆1" loading="lazy"></p><p>1号节点堆化结果：</p><p><img src="/assets/建堆4.c306ac75.png" alt="建堆1" loading="lazy"></p><p>至此，数组所对应的树已经成为了一个最大堆，建堆完成！</p><h3 id="排序" tabindex="-1"><a class="header-anchor" href="#排序" aria-hidden="true">#</a> 排序</h3><p>由于堆顶元素是所有元素中最大的，所以我们重复取出堆顶元素，将这个最大的堆顶元素放至数组末尾，并对剩下的元素进行堆化即可。</p><p>现在思考两个问题：</p><ul><li>删除堆顶元素后需要执行自顶向下（沉底）堆化还是自底向上（上浮）堆化？</li><li>取出的堆顶元素存在哪，新建一个数组存？</li></ul><p>先回答第一个问题，我们需要执行自顶向下（沉底）堆化，这个堆化一开始要将末尾元素移动至堆顶，这个时候末尾的位置就空出来了，由于堆中元素已经减小，这个位置不会再被使用，所以我们可以将取出的元素放在末尾。</p><p>机智的小伙伴已经发现了，这其实是做了一次交换操作，将堆顶和末尾元素调换位置，从而将取出堆顶元素和堆化的第一步(将末尾元素放至根结点位置)进行合并。</p><p>详细过程如下图所示：</p><p>取出第一个元素并堆化：</p><p><img src="/assets/堆排序1.4a22573f.png" alt="堆排序1" loading="lazy"></p><p>取出第二个元素并堆化：</p><p><img src="/assets/堆排序2.26994f33.png" alt="堆排序2" loading="lazy"></p><p>取出第三个元素并堆化：</p><p><img src="/assets/堆排序3.e411601b.png" alt="堆排序3" loading="lazy"></p><p>取出第四个元素并堆化：</p><p><img src="/assets/堆排序4.2b2472be.png" alt="堆排序4" loading="lazy"></p><p>取出第五个元素并堆化：</p><p><img src="" alt="堆排序5" loading="lazy"></p><p>取出第六个元素并堆化：</p><p><img src="" alt="堆排序6" loading="lazy"></p><p>堆排序完成！</p><!--]--></div><!----><footer class="page-meta"><div class="meta-item edit-link"><a href="https://github.com/Snailclimb/JavaGuide/edit/main/docs/cs-basics/data-structure/heap.md" rel="noopener noreferrer" target="_blank" arialabel="编辑此页" class="nav-link label"><!--[--><svg xmlns="http://www.w3.org/2000/svg" class="icon edit-icon" viewbox="0 0 1024 1024" arialabelledby="edit"><title id="edit" lang="en">edit icon</title><g fill="currentColor"><path d="M430.818 653.65a60.46 60.46 0 0 1-50.96-93.281l71.69-114.012 7.773-10.365L816.038 80.138A60.46 60.46 0 0 1 859.225 62a60.46 60.46 0 0 1 43.186 18.138l43.186 43.186a60.46 60.46 0 0 1 0 86.373L588.879 565.55l-8.637 8.637-117.466 68.234a60.46 60.46 0 0 1-31.958 11.229z"></path><path d="M728.802 962H252.891A190.883 190.883 0 0 1 62.008 771.98V296.934a190.883 190.883 0 0 1 190.883-192.61h267.754a60.46 60.46 0 0 1 0 120.92H252.891a69.962 69.962 0 0 0-69.098 69.099V771.98a69.962 69.962 0 0 0 69.098 69.098h475.911A69.962 69.962 0 0 0 797.9 771.98V503.363a60.46 60.46 0 1 1 120.922 0V771.98A190.883 190.883 0 0 1 728.802 962z"></path></g></svg><!--]-->编辑此页<span><svg class="external-link-icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewbox="0 0 100 100" width="15" height="15"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path><polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg><span class="external-link-icon-sr-only">open in new window</span></span><!----></a></div><div class="meta-item update-time"><span class="label">上次编辑于: </span><span class="info">2022/3/3 09:14:56</span></div><div class="meta-item contributors"><span class="label">贡献者: </span><!--[--><!--[--><span class="contributor" title="email: koushuangbwcx@163.com">guide</span><!--]--><!--]--></div></footer><nav class="page-nav"><a href="/cs-basics/data-structure/graph.html" class="nav-link prev" arialabel="图"><div class="hint"><span class="arrow left"></span>上一页</div><div class="link"><!---->图</div></a><a href="/cs-basics/data-structure/tree.html" class="nav-link next" arialabel="树"><div class="hint">下一页<span class="arrow right"></span></div><div class="link">树<!----></div></a></nav><!----><!----></main><!--]--><footer class="footer-wrapper"><div class="footer"><a href="https://beian.miit.gov.cn/" target="_blank">鄂ICP备2020015769号-1</a></div><div class="copyright">Copyright © 2022 Guide</div></footer></div><!--]--><!----><!--]--></div>
    <script type="module" src="/assets/app.93341f6d.js" defer></script>
  </body>
</html>
